// encode: utf-8 (It is best to open using vscode)

#include <iostream>

/*
Fibonacci series: 1 1 2 3 5 8 13 21 ...

Pseudocode:

    when n == 1 and n == 2 then
        arr[1] = arr[2] = 1
    when n > 2 then
        arr[n] = arr[n - 1] + arr[n - 2]

*/

class Solution {
public:
  // 迭代 Iterative
  int fib(int num) {
    int a, b, c;
    a = b = c = 1;

    if (num <= 0)
      return -1;

    for (int i = 3; i <= num; i++) {
      c = a + b;
      a = b;
      b = c; // 如果先把b=c写在a=b之前，那么我们的b的值会被更新，a会拿到一个错误值。
             // a, b = b, c
    }
    return c;
  }

  // 递归 Recursive
  int fib(int num, int) {
    if (num <= 0)
      return -1;
    if (num == 1 || num == 2)
      return 1;
    return fib(num - 1, 1) + fib(num - 2, 1);
  }
};

int main() {
  Solution slt;

  std::cout << slt.fib(12, 1) << std::endl;
  std::cout << slt.fib(44) << std::endl;
}